package leetcode.code0315;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution1 implements IDebug {

	class MyChar {
		char c;
		int index;
		int ans;

		public MyChar(char c, int index) {
			this.c = c;
			this.index = index;
			this.ans = 0;
		}
	}

	public int[] max(String str) {
		char[] cs = str.toCharArray();
		int len = cs.length;
		MyChar[] chars = new MyChar[len];
		for (int i = 0; i < len; i++) {
			chars[i] = new MyChar(cs[i], i);
		}
		this.sort(chars, 0, len - 1);
		int[] ans = new int[len];
		for (int i = 0; i < len; i++) {
			MyChar me = chars[i];
			ans[me.index] = me.ans;
		}
		return ans;
	}

	private void sort(MyChar[] chars, int l, int r) {
		if (l == r) {
			return;
		}
		int m = l + ((r - l) >> 1);
		this.sort(chars, l, m);
		this.sort(chars, m + 1, r);
		this.merge(chars, l, m, m + 1, r);
	}

	private void merge(MyChar[] chars, int l1, int r1, int l2, int r2) {
//		int big1 = 0;
		int big = 0;
		int len = r2 - l1 + 1;
		int start = l1;
		MyChar[] merge = new MyChar[len];
		int p = 0;
		while (l1 <= r1 && l2 <= r2) {
			MyChar c1 = chars[l1];
			MyChar c2 = chars[l2];
			if (c2.c > c1.c) {
//				c2.ans += big2; 错了
				merge[p] = c2;
				big++;
				l2++;
			} else {
				c1.ans += big;
				merge[p] = c1;
				l1++;
			}
			p++;
		}
		while (l1 <= r1) {
			MyChar f = chars[l1];
			f.ans += big;
			merge[p++] = f;
			l1++;
		}
		while (l2 <= r2) {
			MyChar s = chars[l2];
//			s.ans += big2; 错了
			merge[p++] = s;
			l2++;
		}
		p = start;
		for (int i = 0; i < len; i++) {
			chars[p++] = merge[i];
		}
	}

	@Override
	public void debug1() {

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		HelpDebug.print(so.max("acb"));
		HelpDebug.print(so.max("abab"));
		HelpDebug.print(so.max("aosidg"));
		HelpDebug.print(so.max("fabcdfe"));
		HelpDebug.print(so.max("AaBb"));

	}

}
